package month1;

import java.util.*;
import java.util.stream.Collectors;

public class DataStruct {

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int[] arr) {
        if (arr.length < 1) {
            return;
        }
        this.val = arr[0];
        ListNode tmp = this;
        for (int i = 1; i < arr.length; i++) {
            tmp.next = new ListNode(arr[i]);
            tmp = tmp.next;
        }
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public String toString() {
        ListNode tmp = this;
        List<String> strs = new ArrayList<>();
        while (tmp != null) {
            strs.add(tmp.val + "");
            tmp = tmp.next;
        }
        return strs.stream().collect(Collectors.joining(","));
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    public Node(int[] arr) {

    }

    public String toString() {
        List<String> str = new ArrayList<>();
        for (Node tmp = this; tmp != null; tmp = tmp.next) {
            str.add(tmp.val + "");
        }
        return "";
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    TreeNode(Integer[] arr) {

    }

    public String toString() {
        TreeNode node = this;
        Deque<TreeNode> stack = new LinkedList<>();
        List<String> strs = new LinkedList<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                strs.add(node.val+"");
                stack.add(node);
                node = node.left;
            }
            node = stack.pop().right;
        }
        return String.join(",", strs);
    }
}